﻿#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
	//递归    
	//递归是一种解决问题的方法   函数自己调用自己  

	//第一个递归代码（不好的递归）
	//printf("哈哈！\n");    //终止原因   Stack overflow   栈满导致栈溢出  
	//每一次函数调用都要占用一块内存空间：函数栈帧空间（运行时堆栈）    在栈区上申请的空间
	//main();    //此时会死循环的进行打印    但不会无止境的进行打印   会终止程序

	//函数不能无限递归下去    函数的递归必须是有条件的
	//递归的思想：把一个大的复杂问题层层转换为一个与原问题相似  但是规模较小的子问题来求解  直到子问题不能再被拆分 递归结束
	//递归就是把大问题转化成为小问题的过程
	//递归中  递是递推的意思   归是回归的意思

	//汉诺塔问题就是一个递归问题

/*
	递归的限制条件:
	1.递归存在限制条件，当满足这个限制条件，递归便不再继续
	2.每次递归调用后越来越接近这个限制条件
*/

//这是求阶乘的和
//int main()
//{
//
//	printf("请输入n的值：");
//	int n = 0;
//	scanf("%d", &n);
//	int i = 0;
//	int sum = 1;
//	int count = 0;
//	for (i = 1; i <= n; i++)
//	{
//		sum = sum * i;
//		count = count + sum;
//	}
//	printf("1-n阶乘的和为%d\n", count);
//	return 0;
//}

//单独求n的阶乘  阶乘就是所有小于等于该数的正整数的积   并且0的阶乘为1   自然数n的阶乘写作n！
	//n的阶乘公式n！=n*(n-1)!    n为0时阶乘1    阶乘看成一个函数   
	//Fact（n）   1-->n=0       n*Fact(n-1)-->n>0    
//int Fact(int x)   //此处可以用无符号类型进行标识   （unsigned int  x）
//{
//	if (x == 0)    //此处可以进行包含1  因为1和0的阶乘都是1  （x==0||x==1)  
//		//但是尽量少用特殊化  能用递归的公式就尽量用递归公式   即划归到下面的一种情况
//		//  ctrl+shift+/     快速注释
//	{
//		return 1;
//	}
//	//这种情况只有x>0  阶乘只会考虑正整数
//	else 
//	{
//		return x * Fact(x - 1);    
//	//自己调用自己  想求出3的阶乘就要知道2的阶乘  2的阶乘就要知道1的阶乘   这是递：递推  不算值只展开
//	//每一次函数的调用都会返回到上一次函数调用的地方  譬如1的阶乘返回给算2的阶乘的那一步  这是归：回归
//	}
//}
//
//int main()  
//{
//	int n= 0;
//	printf("请输入n的值：");
//	scanf("%d", &n);    //注意n不能太大超出int的最大范围  不考虑溢出的情况
//	int ret = Fact(n);
//	printf("n的阶乘为 %d\n",ret);
//	return 0;
//}


//一个问题有多种解决办法
//1.递归
// 递归特点：使用少量的代码，就能完成很复杂的任务   递推不完成相应的计算  只是对应拆  拆到不能拆后回归
//2.非递归（迭代）

//递归有条件  
//上述代码的返回条件就是n>0,停下来的条件是n==0   一次递归就会接近一次结束条件



//顺序打印整数的每一位
//输入一个数  按顺序打印出来整数的每一位
//譬如：1234    打印1 2 3 4
//输入：520     打印5 2 0 

//递归 
//写一个函数
//void Print(int n)   //只是需要打印每一位   并不需要返回值   void类型
//{
//	if (n > 9)
//	{
//		Print(n / 10);
//		printf("%d ", n % 10);
//	}
//
//	else 
//	{
//		printf("%d ", n % 10);     因为if和else的这两点是一样的   故可以进行简化   简化成下面的代码
//	}
//}

//void Print(int n)
//{
//	//printf("%d ", n % 10);    //如果把输出放在if判断之前那么将不会进行递归   会进行打印4 3 2 1
//
//	if (n > 9)   //递归的条件   停止条件n<=9
//	{
//		Print(n / 10);   //1234会进行调用变123后接着调用变12后接着调用变1     每次递归都在逼近停止条件
//	}
//	printf("%d ", n % 10);   //%10   会输出余数
//}
//
//int main()
//{
//	//写一个打印函数 四位数就把四位数拆成三位数+一位 三位数拆成两位数+一位 两位数拆成一位数+一位  结束的条件就是剩余数字是否是一位
//	printf("请输入一个数：");
//	int i = 0;
//	scanf("%d", &i);
//	Print(i);   //Print函数是用来打印函数的每一位
//	return 0;
//}




//递归和迭代
/*
每一次调用函数 都要开辟一块空间  函数栈帧（函数存放在栈区）回归之后内存才会进行释放  函数不返回那么栈帧空间会一直占用 容易栈溢出
若采用递归进行完成  但是递归层次过深  就会浪费太多的栈帧空间  引起栈溢出（递归会增大内存消耗）

若不想使用递归  就得考虑别的方法  通常是迭代方法（通常是循环）

*/


//求n的阶乘（迭代思想）  累计相乘
//int main()
//{
//	int n = 0;
//	int ret = 1;
//	printf("请输入n的值：");
//	scanf("%d", &n);
//	for (int i = 1; i <= n; i++)
//	{
//		ret *= i;
//	}
//	printf("n的阶乘是%d！\n", ret);
//	return 0;
//}


//也可以
//int Fact(int n)
//{
//	int i = 0;
//	int ret = 1;
//	for (i = 1; i <= n; i++)   	
//	{
//		ret *= i;
//	}
//	return ret;
//}
//
//int main()
//{
//	int n = 0;
//	printf("请输入一个数：");
//	scanf("%d", &n);
//	Fact(n);
//	int ret = Fact(n);
//	printf("n的阶乘是%d", ret);
//	return 0;
//}

//用循环迭代可以提高效率   递归比非递归的形式更加清楚  但是迭代一般比递归的效率更高
//当问题非常复杂  难以使用迭代的方式实现  非递归的方法过于复杂时  递归实现的简洁性就可以补偿他带来的运行时开销
//递归比较难以想到  但是有时候递归就会很简单   写成非递归（迭代）可能要很多行代码
//但是如果递归不恰当书写使用   会导致一些无法接受的后果  那就应该放弃递归   而使用迭代进行解决问题


//数据结构会经常使用递归
//注意递归和非递归的转换要注意


//计算求出第n个斐波那契数    是不适合使用递归求解的    但是斐波那契数通常会通过递归形式描述
//斐波那契数列：1 1 2 3 5 8 13 21 34 55 ...   前两个数的和等于第三个数    前两个数是1    会直接想到递归

//斐波那契可以运用数组
//数组写斐波那契数列
//int main()
//{
//	//数组存储呢  一般最多装47项  一般从第48项开始  就超过了int的可表示范围
//	int arr[47] = { 0,1 };   //把前两项直接初始化成为0 1      如果数组定义为48那么就会越界
//	int i = 1;
//	printf("0 1 ");   //先打印出来前两项   不然后面循环会被忽略
//	for (i = 2; i < 47; i++)    //这里可以i<=46    也可以是i<47   
//	{
//		arr[i] = arr[i - 1] + arr[i - 2];
//		printf("%d ", arr[i]);
//	}
//	return 0;
//}


//打印斐波那契数列的对应项（给出循环次数）
// 
//int main()
//{
//	//打印斐波那契数列的第十项
//	int arr[47] = { 0,1 };
//	int i = 2;
//	int n = 10;
//	int b = 0;
//	for (i = 2; i < n; i++)
//	{
//		arr[i] = arr[i - 1] + arr[i - 2];
//		b = arr[i];     
//	}
//	printf("%d\n",b);
//
//	printf("%d", arr[i - 1]);
//	//注意：在此时 会出现如果不赋值在外面打印arr[i] 但是会打印错误  因为 里面的对应的i是第十项但是下标其实是9 
//	//故小心  选用第一种或者第二种输出
//	return 0;
//}




//递归
//int count = 0;
//
//int Fibo(int n)
//{
//	if (n == 3)
//		count++;    //用count去存储一下n==3的情况被计算了多少次
//	if (n <= 2)
//		return 1;
//	else
//		return(Fibo(n - 1) + Fibo(n - 2));
//}
//
////会导致大量的重复计算   但是层次并不深   递归就不太合适
//
//int main()
//{
//	int n = 0;
//	printf("请输入n的值：");
//	scanf("%d", &n);
//	int ret = Fibo(n);   //斐波那契函数   用ret接收返回值   但是如果过大会导致运行时间过长  或者溢出
//	printf("第n个斐波那契数是%d\n", ret);    //输出102334155
//	printf("count=%d\n", count);   //n=40  最终输出39088169   也就是说n=3的情况计算了39088169次
//	return 0;
//}


//如果想用递归  就用尾递归的方式进行书写   就不会存在  效率的问题

/* 
尾递归是指一个函数在调用自身时，该递归调用是函数的最后一条语句，即函数在调用自身之后不再执行任何操作
而是直接返回递归调用的结果。而普通递归则没有这样的限制，
递归调用可能不是函数的最后一条语句，函数在调用自身之后可能还需要执行其他操作‌

普通递归的定义和过程包括两个阶段：递和归。递阶段涉及函数不断地调用自身，每次传入更小或更简化的参数，直到达到某个特定的终止条件。
归阶段一旦触发终止条件，递归过程开始逆转，从最深层的递归调用回溯，逐层返回并汇聚结果‌

尾递归的特点和优化包括：
尾递归函数的特点是在回归过程中不用做任何操作，这使得大多数现代编译器可以利用这一特点自动生成优化的代码，避免栈溢出的问题。
尾递归优化可以将递归调用转化为循环结构，从而提高程序的效率和性能‌

普通递归在每次调用时都需要保存状态，而尾递归在每次调用后直接返回结果，不需要保存中间状态‌
递归求阶乘
int fact(int n) 
{
	if (n == 0) 
		return 1;
	else 
		return n * fact(n - 1);    递归会把函数再当成计算内容进行计算   保留中间状态
}

尾递归求阶乘
int fact(int n, int total) 
{
	if (n == 0) 
		return total;
	else
		return fact(n - 1, n * total);     尾递归会把函数递归接近结束条件给当成参数传入函数   减少重复运算
}
*/

// 尾递归函数
//int fibonacci(int n, int a, int b) 
//{
//	if (n == 0) 
//	{
//		return a;
//	}
//	else
//	{
//		return fibonacci(n - 1, b, a + b);  //传参传了函数自身的n-1  b  还有a+b
//	}
//}
//
//// 主函数
//int main() 
//{
//	int n;
//	printf("请输入要计算的斐波那契数的位置 n: ");
//	scanf("%d", &n);
//	int result = fibonacci(n, 0, 1);
//	printf("第 %d 个斐波那契数是: %d\n", n, result);
//	return 0;
//}


//迭代(定义三个变量a b c  a+b赋给c  b赋给a  c赋给b   进行向下运算赋值) 
//自己的想法（没写函数  非递归）
//int main()
//{
//	int a = 1;
//	int b = 1;
//	int c = 0;
//	int i = 0;
//	int n = 0;
//	printf("请输入n的值：");
//	scanf("%d", &n);
//	if (n <= 2)
//	{
//		c = 1;
//	}
//
//	else
//	{
//	for (i = 3; i <= n; i++)
//	{
//		c = a + b;
//		a = b;
//		b = c;
//	}
//	}
//	printf("%d", c);
//	return 0;
//}



//实际的方法（非递归（迭代）   速度快）
//int Fib(int n)    //调用函数   但是在函数中执行循环
//{
//	int a = 1;
//	int b = 1;
//	int c = 1;
//	while (n >= 3)     //n大于等于三时才进入循环
//	{
//		c = a + b;
//		a = b;
//		b = c;
//		n--;
//	}
//	return c;
//}
//
//int main()
//{
//	int n = 0;
//	printf("请输入n的值：");
//	scanf("%d", n);
//	int ret=Fib(n);     //斐波那契函数
//	printf("第n个斐波那契数是%d！\n", ret);
//	return 0;
//}




//（*）拓展一下
//青蛙跳台问题（递归的经典问题）
//青蛙一次可以跳1级台阶  也可以跳2级台阶   问跳上第n级台阶   一共有多少中跳法 
//一级台阶：只能一下跳上来  1种  二级台阶：两次一级或者一次两级   2种    三级台阶：三次一级；一次一级一次两级；一次两级一次一级   3种
//四级台阶：四次一级；两次两级；一次两级两次一级；两次一级一次两级；一次一级一次两级一次一级    5种
/*
	此问题把青蛙跳台阶拆分  一级台阶已经确定有一种  二级台阶有两种  三级台阶有三种
	那么四级台阶分解成为三级台阶+一级台阶     五级台阶分为一级台阶+四级台阶==三级台阶+一级台阶+一级台阶 / 三级台阶+两级台阶
	拆分成为了多种已经求解出的多种方法     都是拆分成为  已知级数+一级台阶数
	动态规划问题：用上一步的结果快速计算得到下一步的结果      
	下一步的结果等于上两种结果的相加
	n级台阶：1	2	3	4	5	6		
	跳   法：1	2	3	5	8	13
*/

//非递归
//int main()
//{
//	printf("请输入有多少（n）级台阶：");
//	int n = 0;
//	scanf("%d", &n);    //每一种台阶都会对应一种结果   那么存储可以用数组进行存储
//	int arr[10] = { 0 };
//	arr[0] = 1;
//	arr[1] = 2;
//	int i = 0;
//	int a = arr[0];
//	int b = arr[1];
//	int c = 0;
//	for (i = 2; i < n; i++)    //遍历到n就会结束
//	{
//		c = a + b;
//		a = b;
//		b = c;
//	}
//	printf("一共有%d种方法！", c);
//	return 0;
//}


//递归(尾递归)
//int Jump(int n,int a,int b)
//{
//	if (n == 0)
//	{
//		return b;
//	}
//	else
//	{
//		Jump(n - 1, b, a + b);
//	}
//}
//
//int main()
//{
//	int n = 0;
//	printf("请输入有多少级台阶：");
//	scanf("%d", &n);
//	int ret = Jump(n, 0, 1);
//	printf("n级台阶一共有%d种方法！\n", ret);
//	return 0;
//}
//

//递归（非尾递归）
//int Jump(int n)
//{
//	if (n == 1 || n == 2)
//	{
//		return n;
//	}
//	else
//	{
//		return Jump(n-2) + Jump(n - 1);
//	}
//}
//
//int main()
//{
//	int n = 0;
//	printf("请输入台阶数：");
//	scanf("%d", &n);
//	int ret=Jump(n);
//	printf("%d级台阶一共有%d种方法！\n", n, ret);
//	return 0;
//}



//汉诺塔问题（递归的经典问题）
//一共三根柱子  a柱子上有n个盘子   可以借助b柱子挪到c柱子上   过程得保证每个柱子上  上面的盘子小  下面的盘子大
//把n个盘子抽象成为n-1个盘子和1个盘子

//一个盘子 直接A—>C
//两个盘子 A—>B  A->C  B->C
//三个盘子 A->C  A->B  C->B  A->C  B->A  B->C  A->C
//定义move函数
void move(char pos1,char pos2)
{
	printf(" %c->%c ", pos1, pos2);
}

//n是盘子个数   pos1是A位置(起始位置)  pos2是B位置（中转位置）  pos3是C位置（目的位置）
void Hanoi(int n, char pos1, char pos2, char pos3)  
{
	//递归首先要有结束条件
	if (n == 1)
	{
		move(pos1, pos3);
	}

	else
	{
		Hanoi(n - 1, pos1, pos3, pos2);
		move(pos1, pos3);
		Hanoi(n - 1, pos2, pos1, pos3);
	}
}

int main()
{
	Hanoi(5, 'A', 'B', 'C');
	//定义三个参数   假设64个盘子
	return 0;
}